# 给定一个字符串s，找到s中最长回文子串，可以假设s的最大长度为1000。

stra = "babad"
strb = "cbbd"


def longest_re_substring(s):
    if len(s) > 1000:
        print("Too Long!")
    str_temp = ''
    if s is None or len(s) == 0:
        return str_temp
    for i in range(len(s)):
        j = i - 1
        k = i + 1
        tmp = s[i]
        # tmp为当前字符串，以s[i]起始，若s[k](s[i+1])与s[i]回文，则并入
        # 若tmp前(s[j])后(s[k])相等，则同时并入
        while k < len(s) and s[k] == s[i]:
            tmp = tmp + s[k]
            k += 1
        while j >= 0 and k < len(s) and s[j] == s[k]:
            tmp = s[j] + tmp + s[k]
            j -= 1
            k += 1
        if len(tmp) > len(str_temp):
        # 若len(tmp) >= len(str_temp) 则输出 "aba"
            str_temp = tmp
    return str_temp

print(longest_re_substring(stra))
print(longest_re_substring(strb))


# Manacher算法，时间复杂度O(n)，每个字符两端插入符号如'#'，使所有子串都是奇数长度。
# 输出结果为长度

def Max_Len_of_Substring(s):
    s = '#'+'#'.join(s)+'#'

    RL = [0]*len(s)
    MaxRight = 0
    pos = 0
    MaxLen = 0
    for i in range(len(s)):
        if i < MaxRight:
            RL[i] = min(RL[2*pos-1], MaxRight-i)
        else:
            RL[i] = 1
        while i-RL[i] >= 0 and i+RL[i] < len(s) and s[i-RL[i]] == s[i+RL[i]]:
            RL[i] += 1
        if RL[i]+i-1 > MaxRight:
            MaxRight = RL[i]+i-1
            pos = i
        MaxLen = max(MaxLen, RL[i])
    return MaxLen-1

print(Max_Len_of_Substring(stra))
print(Max_Len_of_Substring(strb))


# 未能全部输出正确结果
# this function Not output right
def Longest_RSubstring(s):
    max = 0
    start = 0
    for i in range(len(s)):
        if i - max >= 1 and s[i - max - 1 : i + 1] == s[i - max - i : i + 1][::-1]:
            start = i - max - 1
            max += 2
            continue
        if i - max >= 0 and s[i - max : i + 1] == s[i - max : i + 1][::-1]:
            start = i - max
            max += 1
    return s[start : start + max]

print(Longest_RSubstring(stra))
print(Longest_RSubstring(strb))
